This paper studies some computability notions for abstract data types, and in particular compares cosemicomputable many-sorted algebras with a notion of finality to model minimal-state realiza-tions of abstract (software) machines. Given a finite many-sorted signature Í
and a set V of visible sorts, for every Í-algebra A with co-r.e. behavior and nontrivial, computable V-behavior, there is a finite signature extension Í' of Í
(without new sorts) and finite set E of
Í'-equations such that A is isomorphic
-- part contents for background part 14
----- text -----
to a reduct of the final (Í', E)-algebra
relative to V. This uses a theorem due
to Bergstra and Tucker (1983). If A is
computable, then A is also isomorphic to the reduct of the initial (Í', E)-algebra.
We also prove some results on congruences of finitely generated free algebras. We show that for every finite signature Í, there are either countably many Í con-gruences on the free Í-algebra or else there is a continuum of such congruences. There are several necessary and sufficient conditions which separate these two cases. We introduce the notion of the Turing degree of a minimal algebra. Using the results above, we prove that there is a fixed one-sorted signature such that for
-- part contents for background part 17
----- text -----
every r.e. degree d, there is a finite set
E of Í-equations such the initial (Í, E)-algebra has degree d. There is a two-sorted signature Í‚ and a single visible sort such that for every r.e. degree d there is a finite set E of Í-equations such that the initial (Í, E, V)-algebra is computable and the final (Í, E,V)-algebra is cosemi-computable and has degree d.
